#define DEBUG
#include <cstdio>
#define MAXK 2000
#define MAXC 1000000

using namespace std;

long long mul(long long a, long long b, long long p) {
  return (((a/MAXC*b)%p*MAXC%p)+((a%MAXC*b)%p))%p;
}

long long qpower(long long a, long long n, long long p) {
  long long s=1;
  for (; n>1; n>>=1) {
    if (n&1) {
      s = mul(s, a, p);
    }
    a = mul(a, a, p);
  }
  return mul(s, a, p);
}

long long solve(long long n, long long k, long long a[][MAXK+1], long long s[][MAXK+1], long long p) {
  long long ans=0, temp;
  for (long long i=0; i<=k; i++) {
    temp=s[k][i];
    bool flag=false;
    for (long long j=n-i+1; j<=n+1; j++) {
      if (j%(i+1)!=0 || flag) {
	temp = mul(temp, j, p);
      } else {
	flag = true;
	temp = mul(temp, j/(i+1), p);
      }
    }
    ans = (ans+temp)%p;
  }
  return ans;
}

int main() {
#ifdef DEBUG
  freopen("0.in", "r", stdin);
  freopen("0.out", "w", stdout);
#endif

  long long k, n, m, p;
  scanf("%lld %lld %lld %lld", &k, &n, &m, &p);

  if (k>2000) {
    long long ans=0;
    for (long long i=m; i<=n; i++) {
      ans = (qpower(i, k, p)+ans)%p;
    }
    printf("%lld", ans);
  } else {
    static long long a[MAXK+1][MAXK+1], s[MAXK+1][MAXK+1];
    s[0][0] = a[0][0] = 1;
    for (int i=1; i<=k; i++) {
      a[i][0] = 1;
      s[i][0] = 0;
      for (int j=1; j<=k; j++) {
	a[i][j] = (a[i-1][j-1]+a[i-1][j])%p;
	s[i][j] = (s[i-1][j-1]+mul(s[i-1][j], j, p))%p;
      }
    }
    printf("%lld", (solve(n, k, a, s, p)+p-solve(m-1, k, a, s, p))%p);
  }

  fcloseall();
  return 0;
}
